package style.Leetcode.初级算法.linkedList.linkedList_20220821_1_回文链表;

import style.Leetcode.初级算法.linkedList.ListNode;

/**
 * 回文链表
 *
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 *
 * 输入：head = [1,2,2,1]
 * 输出：true
 *
 * 输入：head = [1,2]
 * 输出：false
 */
public class Solution {

    /**
     * 快慢指针
     *      快指针
     */
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
        // 快慢指针找到中点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 如果fast不为空，说明链表的长度为奇数
        if (fast != null) {
            slow = slow.next;
        }

        // 反转后半部分链表
        slow = reverse(slow);

        fast = head;
        while (slow != null) {
            if (fast.val != slow.val) {
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;

    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode list1 = new ListNode(1);
        list1.next = new ListNode(2);
        list1.next.next = new ListNode(2);
        list1.next.next.next = new ListNode(1);
        System.out.println(solution.isPalindrome(list1));
    }
}
